package cn.handong.tool.algorithm;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 1墙壁
 * 0通道
 */
public class MyTest {
    static String[][] a;
    static int n;
    static int m;
    static BfsNode S = new BfsNode();
    static BfsNode T = new BfsNode();
    static int[] X = {0,0,1,-1};
    static int[] Y = {1,-1,0,0};
    static int res = 0;

    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
        n = 5;
        m = 5;
        a = new String[n][m];
//        scanner.nextLine();
        String[] strs = new String[]{".....",
                                     ".*.*.",
                                     ".*S*.",
                                     ".***.",
                                     "....*"};
        for (int i = 0; i < n; i++) {
            String[] str = strs[i].split("");
            for (int j = 0; j < m; j++) {
                a[i][j] = str[j];
            }
        }
//        scanner.nextLine();
        //起点   终点
        S.x = 2;
        S.y = 2;
        T.x = 4;
        T.y = 3;
        System.out.println(myBfs());
    }

    private static int myBfs() {
        Queue<BfsNode> queue = new LinkedList<>();
        queue.offer(S);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                BfsNode node = queue.poll();
                if (node.x == T.x && node.y == T.y){
                    return res;
                }
                for (int j = 0; j < 4; j++) {
                    int newX = node.x + X[j];
                    int newY = node.y + Y[j];
                    if (newX >= 0 && newX < n && newY >= 0 && newY < m && Objects.equals(a[newX][newY], ".")){
                        BfsNode newNode = new BfsNode();
                        newNode.x = newX;
                        newNode.y = newY;
                        queue.offer(newNode);
                        a[newX][newY] = "*";
                    }
                }
            }
            res++;
        }
        return 0;
    }
}


class BfsNode{
    int x;
    int y;
}

/**
 * DFS(Depth First Search) 深度优先遍历
 * BFS(Breadth First Search) 广度优先遍历
 */